package main

import "fmt"

/*
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。
这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中
*/
func main() {
	head := newNode(1, nil, nil, nil)
	list := newNode(2, nil, nil, nil)
	head.Child = list
	list2 := newNode(3, head, nil, nil)
	list.Child = list2
	root := flatten(head)
	//	fmt.Printf("%#v\n", root.Next.Next.Prev.Prev)
	for {
		fmt.Printf("%#v\n", root.Val)
		if root.Next == nil {
			break
		}
		root = root.Next
	}
}

type Node struct {
	Val   int
	Prev  *Node
	Next  *Node
	Child *Node
}

func newNode(val int, prev, child, next *Node) *Node {
	return &Node{
		Val:   val,
		Prev:  prev,
		Child: child,
		Next:  next,
	}
}

/**
 *	flatten
 *	@Description: 动态规划
 *	@param root *Node
 *	@return res *Node
 */
func flatten(root *Node) (res *Node) {
	res = root
	if root == nil {
		return res
	}
	tmpHead := root
	for {
		if root.Child != nil {
			tmpNext := root.Next
			root.Child.Prev = root
			root.Next, root.Child = root.Child, nil
			for root.Next != nil {
				root = root.Next
			}
			root.Next = tmpNext
			if tmpNext != nil {
				tmpNext.Prev = root
			}
		}
		root = tmpHead.Next
		tmpHead = tmpHead.Next
		if root.Next == nil && root.Child == nil {
			break
		}
	}
	return res
}
